데이터베이스 인덱스는 왜 'B-Tree'를 선택하였는가

 

데이터베이스의 탐색 성능을 좌우하는 인덱스.

인덱스는 데이터 저장, 수정, 삭제에 대한 성능을 희생시켜 탐색에 대한 성능을 대폭 상승하는 방식이라 볼 수 있다.
DB의 인덱스는 B-tree 자료구조를 이용하여 테이블의 요소를 빠르게 탐색하도록 설계되어있다.

그러면 인덱스는 그 많은 자료구조 중에 왜 하필 'B-tree'를 사용하는 것일까?

참고로 해당 글에서는 데이터베이스의 인덱스가 무엇인지에 대해서는 다루지 않는다. 하지만 인덱스에 대해 잘 몰라도 이 글을 읽는 것에 큰 어려움이 없을 것이다. DB를 직접 다루는 개발자가 아니더라도 SW 성능에 관심이 많거나 자료구조, 알고리즘 공부를 하는 사람이라면 관심을 가지고 읽어볼 만한 글이 될 것 같다.

인덱스가 B-Tree를 이용하는 이유에 대해 알기 위해, B-Tree의 하위 개념인 트리(Tree)에 대해 먼저 알아보자.

 

자료구조 트리(Tree) 란?

Average case of Tree algorithm 

우선 Tree 구조에 대해서는 잘 알고 있을 것이다.
일반적인 Tree는 평균적으로 탐색에 대한 시간 복잡도로 O(logN)을 가진다.

그러나 이는 지극히 '평균적인' 시간 복잡도이며, 최악의 경우에는 이야기가 달라진다.  

Worse case of Tree algorithm 

만약 트리 노드의 요소가 위처럼 한쪽 방향으로만 쏠려있다면 최악의 탐색 시간은 O(N)을 가지게 된다.
이러한 경우를 방지하기 위해 우리는 밸런스 트리(Balanced Tree)를 이용할 수 있다.

💡 밸런스 트리(Balanced Tree)란?
트리의 노드가 한 방향으로 쏠리지 않도록, 노드 삽입 및 삭제 시 특정 규칙에 맞게 재 정렬되어 왼쪽과 오른쪽 자식 양쪽 수의 밸런스를 유지하는 트리이다. 항상 양쪽 자식의 밸런스를 유지하므로, 무조건 O(logN)의 시간 복잡도를 가지게 된다.
다만 재정렬되는 작업으로 인해 노드 삽입 및 삭제 시 일반적인 트리보다 성능이 떨어지게 된다. 그러므로 밸런스 트리는 삽입/삭제의 성능을 희생하고 탐색에 대한 성능을 높였다고 볼 수 있다. 

밸런스 트리는 대표적으로 RedBlack-Tree, B-Tree가 있다.

 

위에 설명한 것처럼 밸런스 트리는 최악의 경우에도 O(logN)이므로, 탐색시간에 매우 효율적인 자료구조이다. 그래서 데이터베이스의 인덱스는 밸런스 트리, 그중 B-Tree를 선택했다.

자, 이제 여기서 자료구조에 대해 어느 정도 아는 사람들이라면 이러한 의아함을 가지게 될 것이다.

 

"왜 하필 B-Tree지?"
"탐색 시간이 O(logN)인 자료구조나 알고리즘은 다른 것들도 많지 않나?" 
"해시 테이블은 O(1)인데, 그러면 차라리 해시 테이블을 쓰는 게 더 빠르지 않나?"
"그러면 밸런스 트리 중 B-Tree 말고도 RedBlack-Tree로도 사용할 수 있는 것 아닌가?"

 

아니면 이제 위의 글을 읽고서야, "어, 그러게? 그러고 보니 왜 굳이 B-Tree를 쓰는 거지?"라고 생각할 수도 있다.
당연하게도 굳이 B-Tree를 사용한 이유가 있으며, 그러한 이유를 알아보는 것이 이 글의 메인 핵심이다. 

지금부터 그러한 이유가 도대체 무엇인지 하나씩 알아보도록 하자.

 

탐색시간이 제일 빠른 해시 테이블을 DB 인덱스로 사용할 수 없는 이유

모든 자료구조와 그 어떤 알고리즘을 비교해도 탐색 시간이 가장 빠른 것은 바로 해시 테이블이다. 해시 테이블은 해시 함수를 통해 나온 해시 값을 이용하여 저장된 메모리 공간에 한 번에 접근을 하기 때문에 O(1)이라는 시간 복잡도를 가진다. (물론 해시 충돌 등으로 최악의 경우에 O(N)이 될 수 있지만, 평균적으로는 O(1)으로 볼 수 있다)

그러나 이는 온전히 '단 하나의 데이터를 탐색하는 시간' 에만 O(1)이다. 예를 들어 1,2,3,4,5가 저장되어 있는 해시 테이블에서 3이라는 데이터를 찾을 때에만 O(1)이라는 것이다. (3이라는 데이터를 인풋으로 해시 함수를 통해 나온 해시 값으로 3이 저장된 메모리 공간에 접근을 할 것이기 때문이다)

'그게 무엇이 문제이냐'라고 생각한다면 잠깐 이 부분을 놓쳤을 것이다.

 

우리는 DB에서 등호(=) 뿐 아니라 부등호(<, >)도 사용할 수 있다는 것을.

 

모든 값이 정렬되어있지 않으므로, 해시 테이블에서는 특정 기준보다 크거나 작은 값을 찾을 수 없다. 굳이 찾으려면 찾을 수는 있지만 O(1)의 시간 복잡도를 보장할 수 없고 매우 비효율적이다.

그렇기에 기준 값보다 크거나 작은 요소들을 항상 탐색할 수 있어야 하는 DB 인덱스 용도로 해시 테이블은 어울리지 않는 자료구조인 것이다.

 

"해시 테이블을 사용하지 못하는 이유는 납득이 되었다.
그러면 탐색이 O(logN)인 다른 자료구조나 알고리즘은 왜 사용하지 못하는 것일까?"

 

아까 밸런스 트리를 살짝 설명하면서, 트리 종류로 B-Tree와 RedBlack-Tree를 소개하였다. 같은 밸런스 트리 종류임에도 RedBlack-Tree는 DB 인덱스로 선택받지 못한 이유가 궁금할 것이다.

먼저 이 두 개가 어떻게 다른지 개념을 살짝 설명하도록 한다.

 

RedBlack-Tree와 B-Tree의 특징 비교

RedBlack-Tree의 특징

각 노드는 하나의 값만 가진 상태로 좌, 우 자식 노드의 개수 밸런스를 맞춘다. 빨간색, 검은색 노드로 구분되어 있는 것은 노드의 삽입/삭제 작업을 할 때마다 규칙에 맞게 재정렬을 하기 위한 수단이므로 여기서는 크게 신경 쓰지 않아도 된다.
(RedBlack-Tree에 대해 더 자세히 알고 싶다면 여기를 참조. 개념이 크게 어렵지는 않다.)

 

B-Tree의 특징

B-Tree는 위처럼 노드 하나에 여러 데이터가 저장될 수 있다. 각 노드 내 데이터들은 항상 정렬된 상태이며, 데이터와 데이터 사이의 범위를 이용하여 자식 노드를 가진다. 그러므로 자식 노드 개수는 (n+1)을 가진다. 

 

이처럼, 위 두 개의 트리는 항상 좌, 우 자식노드 개수의 밸런스를 유지하므로 최악의 경우에도 무조건 탐색 시간이 O(logN)을 가지게 된다.
이것만 보면 B-Tree 뿐 아니라, RedBlack-Tree도 DB 인덱스로 사용하기에는 큰 문제가 없어 보인다.
그러면 도대체 왜 RedBlack-Tree는 DB 인덱스로 선택받지 못한 것일까.

 

이 글을 읽는 여러분들이 아래로 스크롤을 내리기 전, 직접 한번 고민해보는 시간을 가지면 좋을 것 같다.
고민을 직접 해보고 해답을 알아가는 것이 머릿속으로 더 깊게 받아들일 수 있을 것이라 생각한다. 직접 알아낸다면 더욱 베스트이다.

 

 

RedBlack-Tree가 DB 인덱스로 선택받지 못한 이유

RedBlack-Tree와 B-Tree의 차이는 무엇일까?

위의 사진만 봐도 알 수 있듯이, 이 둘의 가장 큰 차이는 '하나의 노드가 가지는 데이터 개수'이다. RedBlack-Tree는 무조건 하나의 노드에 하나의 데이터 요소만을, B-Tree는 하나의 노드에 여러 개의 데이터 요소를 저장한다.

 

표시한 부분을 한번 보자. 마치 배열처럼 정렬이 되어있다. 
맞다. 배열이다. 실제 메모리 상에 차례대로 저장이 되어있는 것이다. 같은 노드 공간의 데이터들끼리 굳이 자식 노드처럼 참조 포인터 값으로 접근할 필요가 없다.

이는 즉, 같은 노드 상 데이터를 탐색할 때는 포인터 접근을 하는 것이 아니라 실제 메모리 디스크에서 바로 다음 인덱스의 접근을 하는 것이다. 혹시나 이해하기 어려울까 하여 위 사진을 예시로 아래에 조금 더 쉽게 정리해본다.

# 탐색 방식 순서

1. 200이라는 값이 있는지 확인하기 위해, 100, 155, 226이 저장되어 있는 Root 노드에 있는 데이터들을 탐색한다. 실제 메모리 디스크 상 순차적으로 저장되어 있는 데이터들을 빠르게 탐색한다.

2. Root 노드에 200이 없다. 200은 155와 226 사이의 값이므로, 해당 범위에 존재하는 자식 노드를 가리키는 포인터가 존재하는지 확인한다. 있으면 포인터를 통해 해당 자식 노드로 접근한다. 자식 노드는 168, 200의 값을 가지고 있다.

3. 실제 메모리 디스크 상 순차적으로 저장되어 있는 168, 200의 값을 빠르게 탐색한다. 찾으려 했던 200의 값을 찾아낸다.

 

 

다시 RedBlack-Tree를 봐보도록 하자.

RedBlack-Tree는 B-Tree와 다르게 각 노드마다 무조건 하나의 데이터만 가지게 되므로 모든 데이터를 접근할 때 무조건 참조 포인터로 접근을 하게 된다. 따라서 B-Tree의 배열 형식의 접근과 RedBlack-Tree의 참조 포인터 접근의 시간 차이를 알아야 한다.

사실 이 둘 다 시간 복잡도는 O(logN)이란 것은 변함이 없다.
그러나 이러한 시간 복잡도는 알고리즘 처리에 대한 이론적인 시간 계산 방식일 뿐이다. 물리적, 절대적인 시간 개념으로는 배열 접근이 훨씬 빠를 수밖에 없다.

참조 포인터로 메모리에 접근한다는 것은, 실제 메모리 상 순서대로 저장이 되었든 안 되었든 접근하려는 주소를 연산을 통해 직접 알아내어 데이터에 접근한다는 것이다. 주소를 알아내는데 CPU 내부적으로 많은 연산을 수행하게 될 것이다.

이와 반대로 배열은 데이터들이 메모리 공간에 차례대로 저장이 되어 있으므로 접근할 주소를 바로 알 수 있다. 그래서 메모리 주소를 알아내는데 성능이 영향이 없다. 비록 B-Tree도 자식 노드를 접근할 땐 참조 포인터로 접근을 하지만, 하나의 노드가 가지는 데이터 개수가 많아질수록 포인터 개수는 확연히 줄어들고, 트리 내에서 다루는 데이터가 많아질수록 이러한 차이는 더욱 커질 것이다.

비록 같은 O(logN)이지만, 포인터 접근 수의 차이로 인해 B-Tree가 RedBlack-Tree보다 탐색 시간이 더 빠를 수밖에 없다.
솔직히 이 둘의 성능 차이는 웬만한 데이터 개수로는 차이가 없겠지만, 글로벌하게 데이터를 다루는 수준이라면 이러한 차이가 분명 큰 영향이 생기지 않을까 생각한다.

 

💡 B-Tree에서 시간 복잡도는 노드 배열 참조 시간 O(logN)과 자식 노드들 탐색 시간 O(logM)으로 따로 계산되어야 하는 것 아닌가요?

일반적으로 B-Tree는 하나의 노드에 저장될 노드 개수를 상수로 제한한다. 쉽게 말해서 노드 내 데이터 개수를 무제한으로 저장하는 것이 아니라, 최대 3,5개 등으로 저장하여 사용한다는 것이다.
따라서 무조건 일반적으로 B-Tree의 시간 복잡도를 계산할 때는 노드 탐색 시간은 상수로 취급하여 시간 복잡도 계산에서 제외된다.

Why is b-tree search O(log n)?

 

위에서 설명한 것처럼, 같은 밸런스 트리임에도 RedBlack-Tree를 사용하지 않는 이유는 '참조 포인터 접근'의 수 때문이었다.

 

"참조 포인터가 문제라면 그냥 참조 요소 자체가 없는 배열을 쓰면 되지 않나?"

 

배열을 쓴다... 괜찮은 방법이다.
충분히 요소들이 정렬 상태를 유지하고 있다면 어쩌면 배열로도 무리가 없을 것 같아 보인다.

하지만 배열 역시 DB 인덱스로 선택받지 못한 이유가 있다. 바로 아래에서 배열을 쓰지 못하는 이유를 알아보도록 하자.

 

데이터 접근이 빠른 자료구조 '배열'이 DB 인덱스로 선택받지 못한 이유

배열은 참조 포인터라는 개념이 없고, 모든 데이터가 메모리 상 차례대로 저장되어 있어 접근이 매우 빠르다.
참조가 없으니 당연히 탐색 속도로만 본다면 B-Tree보다 훨씬 빠르다. 뿐만 아니라, 해시 테이블과는 다르게 데이터들을 정렬 상태로 유지할 수 있으므로 부등호(< , >) 연산에도 문제가 없다.

하지만 배열이 B-Tree보다 빠른 것은 '탐색'뿐이다.

배열 내에서 데이터 저장, 삭제가 일어나는 순간 B-Tree보다 훨씬 비효율적인 성능이 발생하게 된다.

출처 :&amp;amp;nbsp;https://www.geeksforgeeks.org/search-insert-and-delete-in-a-sorted-array/

 

배열 자료구조를 정확히 알고 있다면, 위 사진이 바로 이해가 될 것이다.

위 사진처럼 중간에 3이라는 데이터를 삽입하게 되면, 삽입될 해당 자리를 찾은 뒤 3보다 큰 데이터들은 한 칸씩 뒤로 물러나게 된다. 이때 뒤로 한 칸씩 이동하는 과정에서 평균 시간 복잡도가 O(N)이 걸리게 된다. 마치 데이터들이 다 같이 "자~ 하나, 둘, 셋!" 하며 동시에 이동하지 않는 한, 실제로는 CPU 연산에 의해 맨 뒤에 데이터부터 시작해서 각 한 칸씩 뒤로 이동하는 작업을 모두 거치게 될 것이다.

그나마 새롭게 삽입되는 데이터가 가장 큰 데이터라서 바로 맨 뒤에 저장된다면 O(logN)이 걸리겠지만(탐색 시간이 있기 때문), 최악의 경우인 가장 작은 데이터라면, 자리 탐색 시간인 O(logN)과 맨 앞에 새로운 데이터 삽입을 위해 모든 데이터를 한 칸씩 뒤로 이동하는 시간 O(N)으로, 총 O(N*logN)의 시간이 걸리게 된다.
(정정: 하나의 요소에 대한 삽입,삭제는 O(N+logN) = O(N)의 시간이 걸리게 됩니다.
잘못된 부분을 캐치해주신 'vince joe'님께 감사드립니다.)

이는 새로운 데이터 저장뿐 아니라, 삭제 시에도 동일하다. 
삭제의 경우에는, 특정 데이터를 삭제하면 중간에 삭제된 데이터의 공간을 메꾸기 위해 뒤에서 한 칸씩 앞으로 이동하는 과정인 O(N)이 걸리게 되는 문제가 있기 때문이다.

데이터 수정이 일어날때도 퀵 정렬, 병합 정렬 등 배열 자료구조에서 O(N*logN) 시간으로 재정렬을 이루어야 한다는 점도 있다.

참고로 B-tree의 삽입, 삭제는 트리의 높이(h)에 따른 O(h)의 시간 복잡도를 가지는데, 이는 logN보다 훨씬 작은 값이다.

 

모든 면으로 DB 인덱스 용도로 가장 적합한 자료구조인 B-Tree

결론적으로 DB 인덱스로 B-Tree가 가장 적합한 이유들을 정리하면 아래와 같다.

1. 항상 정렬된 상태로 특정 값보다 크고 작은 부등호 연산에 문제가 없다.
2. 참조 포인터가 적어 방대한 데이터 양에도 빠른 메모리 접근이 가능하다.
3. 데이터 탐색뿐 아니라, 저장, 수정, 삭제에도 항상 O(logN)의 시간 복잡도를 가진다.

자료구조와 알고리즘에는 정말 다양한 방식, 다양한 구조가 존재한다. 많이 비슷하면서도 약간의 특징만 달라짐으로 인해 어느 용도에 적합한지 구분이 되어버릴 정도로, 자료구조 사용과 알고리즘 구현에 작은 요소 하나하나가 매우 중요한 것을 몸소 느낄 수 있었다. 

어떤 소프트웨어 개발을 하더라도 작은 요소 하나하나 최대한 신중하게 결정하도록 노력해야겠다.

 

---

[2022.02.03일 추가내용]

배열에서 삽입,삭제가 느리다면, 포인터 LinkedList를 사용하면 되지 않나요?

 

LinkedList는 삽입, 삭제 시, 중간의 포인터를 잠깐 끊고, 추가될 요소 혹은 삭제할 요소를 처리한 다음, 다시 포인터로 연결만 하면 되기 때문에 배열에서 가지고 있던 삽입,삭제 문제를 한번에 해결할 수 있다.

삽입, 삭제도 빠르니 LinkedList는 어떨까? 충분히 B-tree를 대체할 수 있지 않을까 생각이 든다.
하지만 역시 LinkedList도 B-Tree를 대체할 수 없는 이유가 있다. 

 

아래에서 그 이유를 확인해보기 전에 먼저 직접 깊히 그 이유를 생각해보면 좋을 것 같다.

 

 

LInkedList가 DB 인덱스로 선택받지 못한 이유

geeksforgeeks.org/linkedlist-getlast-method-in-java/

 

배열이 탐색에서 빠른 이유가 무엇일까?
먼저 배열은 정렬이 된 상태와 되어있지 않은 상태가 있을 것이다. 정렬이 되어 있다면 이진탐색(Binary Search)이 가능하며 이는 O(logN)의 시간을 보장한다.
이와 반대로 정렬이 되어 있지 않다면, Quick Sort, Merge Sort 등의 시간 복잡도(Time Complexity)가 Average O(NlogN)인 알고리즘을 사용한다면 빠르게 정렬을 시킬 수 있다.

하지만 이 알고리즘들은 어떻게 돌아가는가?
배열의 총 길이를 미리 알아야 하고, Divided and Conquer가 일어날 때마다 해당되는 Index Number가 파악이 가능해야 하며, Index Number 파악을 위해선 기존에 파악되어있는 다른 IndexNumber 정보들을 이용해 또 다시 계산이 되어야 한다.

LinkedList에 Index Number라는 개념이 있던가?
또한 각 요소에 Index Number 정보들을 추가로 가지고 있다 해도, 그 Index Number로 해당 요소로 바로 접근을 할 수 있는가?


참조 포인터로만 이루어져 있는 LinkedList에서는 이러한 알고리즘을 적용할 수 없다.

탐색을 무조건 제일 앞 부분인 'HEAD'부터 시작해야 하는 LinkedList로서는, DB-Index로 사용하기엔 매우 비효율적인 자료구조가 되는 셈인 것이다.

(LinkedList 관련하여 질문해주신 '지니의 Step'님께 감사드립니다.)